/****************************************************
          File Name:mergei_sort.c
          Author: Abby Cin
          Mail: abbytsing@gmail.com
          Created Time: Mon 06 Apr 2015 06:49:23 PM CST
*****************************************************/

#include<stdio.h>
#include<stdlib.h>

void merge(int A[], int p, int q, int r)
{
    int n1 = q - p + 1;
    int n2 = r - q;
    int k, i, j;

    int L[n1 + 1];
    int M[n2 + 1];

    for(i = 0; i < n1; i++)
        L[i] = A[p + i -1];
    for(j = 0; j < n2; j++)
        M[j] = A[q + j];

    L[n1] = RAND_MAX;
    M[n2] = RAND_MAX;

    i = 0;
    j = 0;

    for(k = p-1; k < r; k++)
    {
        if(L[i] <= M[j])
        {
            A[k] = L[i];
            i = i + 1;
        }
        else
        {
            A[k] = M[j];
            j = j+ 1;
        }
    }
}  

void merge_improve(int A[], int p, int q, int r)
{
    int n1 = q - p + 1;
    int n2 = r - q;
    int k, i, j;

    int L[n1];
    int M[n2];

    for(i = 0; i < n1; i++)
        L[i] = A[p + i -1];
    for(j = 0; j < n2; j++)
        M[j] = A[q + j];

    i = 0;
    j = 0;

    for(k = p-1; k < r; k++)
    {
        if(i == n1 || j == n2)
        {
            if(i == n1)
                A[k] = A[i];
            else
                A[k] = A[j];
        }else{
            if(L[i] <= M[j]) 
            {
                A[k] = L[i];
                i = i + 1;
            }
            else
            {
                A[k] = M[j];
                j = j+ 1;
            }
        }
    }
}  

void merge_sort(int A[], int p, int r)
{
    int q;

    if(p < r)
    {
        q = (p + r) / 2;
        merge_sort(A, p, q);
        merge_sort(A, q+1, r);
        
        merge_improve(A, p, q, r);
    }
}

int main(int argc, char *argv[])
{
    int len = atoi(argv[1]);
    int array[len];
    int i;

    for(i = 0; i < len; i++)
        array[i] = rand();
    merge_sort(array, 1, len);
/*
    for(i=0; i<len; i++)
        printf("%d ", array[i]);
*/        
    printf("\n");

    return 0;
}
